package leetcode_1001_1100;

import java.util.*;

public class LeeCode_1163 {
    public static void main(String[] args) {
        System.out.println(lastSubstring("abab"));
        System.out.println(lastSubstring("leetcode"));
        System.out.println(lastSubstring("cacacb"));
    }
    private static String lastSubstring(String s) {
        int i = 0, j = i + 1, n = s.length();
        while (j < n){
            int k = 0;
            while (j + k < n && s.charAt(j + k) == s.charAt(i + k)){
                k++;
            }
            if (j + k < n && s.charAt(j + k) > s.charAt(i + k)){
                int t = i;
                i = j;
                j = Math.max(j + 1, t + k + 1);
            }else {
                j = j + k + 1;
            }
        }
        return s.substring(i);
    }
}
